/*
 * Copyright (C) 2010 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.ssa;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.List;

import com.android.dx.rop.code.Exceptions;
import com.android.dx.rop.code.FillArrayDataInsn;
import com.android.dx.rop.code.Insn;
import com.android.dx.rop.code.PlainCstInsn;
import com.android.dx.rop.code.PlainInsn;
import com.android.dx.rop.code.RegOps;
import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.rop.code.Rop;
import com.android.dx.rop.code.Rops;
import com.android.dx.rop.code.ThrowingCstInsn;
import com.android.dx.rop.code.ThrowingInsn;
import com.android.dx.rop.cst.Constant;
import com.android.dx.rop.cst.CstLiteralBits;
import com.android.dx.rop.cst.CstMethodRef;
import com.android.dx.rop.cst.CstNat;
import com.android.dx.rop.cst.CstString;
import com.android.dx.rop.cst.CstType;
import com.android.dx.rop.cst.TypedConstant;
import com.android.dx.rop.cst.Zeroes;
import com.android.dx.rop.type.StdTypeList;
import com.android.dx.rop.type.Type;
import com.android.dx.rop.type.TypeBearer;

/**
 * Simple intraprocedural escape analysis. Finds new arrays that don't escape
 * the method they are created in and replaces the array values with registers.
 */
public class EscapeAnalysis {

	/**
	 * Struct used to generate and maintain escape analysis results.
	 */
	static class EscapeSet {

		/** set containing all registers related to an object */
		BitSet regSet;
		/** escape state of the object */
		EscapeState escape;
		/** list of objects that are put into this object */
		ArrayList<EscapeSet> childSets;
		/** list of objects that this object is put into */
		ArrayList<EscapeSet> parentSets;
		/** flag to indicate this object is a scalar replaceable array */
		boolean replaceableArray;

		/**
		 * Constructs an instance of an EscapeSet
		 * 
		 * @param reg
		 *            the SSA register that defines the object
		 * @param size
		 *            the number of registers in the method
		 * @param escState
		 *            the lattice value to initially set this to
		 */
		EscapeSet(int reg, int size, EscapeState escState) {
			regSet = new BitSet(size);
			regSet.set(reg);
			escape = escState;
			childSets = new ArrayList<EscapeSet>();
			parentSets = new ArrayList<EscapeSet>();
			replaceableArray = false;
		}
	}

	/**
	 * Lattice values used to indicate escape state for an object. Analysis can
	 * only raise escape state values, not lower them. TOP - Used for objects
	 * that haven't been analyzed yet NONE - Object does not escape, and is
	 * eligible for scalar replacement. METHOD - Object remains local to method,
	 * but can't be scalar replaced. INTER - Object is passed between methods.
	 * (treated as globally escaping since this is an intraprocedural analysis)
	 * GLOBAL - Object escapes globally.
	 */
	public enum EscapeState {
		TOP, NONE, METHOD, INTER, GLOBAL
	}

	/** method we're processing */
	private SsaMethod ssaMeth;
	/** ssaMeth.getRegCount() */
	private int regCount;
	/** Lattice values for each object register group */
	private ArrayList<EscapeSet> latticeValues;

	/**
	 * Constructs an instance.
	 * 
	 * @param ssaMeth
	 *            method to process
	 */
	private EscapeAnalysis(SsaMethod ssaMeth) {
		this.ssaMeth = ssaMeth;
		this.regCount = ssaMeth.getRegCount();
		this.latticeValues = new ArrayList<EscapeSet>();
	}

	/**
	 * Finds the index in the lattice for a particular register. Returns the
	 * size of the lattice if the register wasn't found.
	 * 
	 * @param reg
	 *            {@code non-null;} register being looked up
	 * @return index of the register or size of the lattice if it wasn't found.
	 */
	private int findSetIndex(RegisterSpec reg) {
		int i;
		for (i = 0; i < latticeValues.size(); i++) {
			EscapeSet e = latticeValues.get(i);
			if (e.regSet.get(reg.getReg())) {
				return i;
			}
		}
		return i;
	}

	/**
	 * Finds the corresponding instruction for a given move result
	 * 
	 * @param moveInsn
	 *            {@code non-null;} a move result instruction
	 * @return {@code non-null;} the instruction that produces the result for
	 *         the move
	 */
	private SsaInsn getInsnForMove(SsaInsn moveInsn) {
		int pred = moveInsn.getBlock().getPredecessors().nextSetBit(0);
		ArrayList<SsaInsn> predInsns = ssaMeth.getBlocks().get(pred).getInsns();
		return predInsns.get(predInsns.size() - 1);
	}

	/**
	 * Finds the corresponding move result for a given instruction
	 * 
	 * @param insn
	 *            {@code non-null;} an instruction that must always be followed
	 *            by a move result
	 * @return {@code non-null;} the move result for the given instruction
	 */
	private SsaInsn getMoveForInsn(SsaInsn insn) {
		int succ = insn.getBlock().getSuccessors().nextSetBit(0);
		ArrayList<SsaInsn> succInsns = ssaMeth.getBlocks().get(succ).getInsns();
		return succInsns.get(0);
	}

	/**
	 * Creates a link in the lattice between two EscapeSets due to a put
	 * instruction. The object being put is the child and the object being put
	 * into is the parent. A child set must always have an escape state at least
	 * as high as its parent.
	 * 
	 * @param parentSet
	 *            {@code non-null;} the EscapeSet for the object being put into
	 * @param childSet
	 *            {@code non-null;} the EscapeSet for the object being put
	 */
	private void addEdge(EscapeSet parentSet, EscapeSet childSet) {
		if (!childSet.parentSets.contains(parentSet)) {
			childSet.parentSets.add(parentSet);
		}
		if (!parentSet.childSets.contains(childSet)) {
			parentSet.childSets.add(childSet);
		}
	}

	/**
	 * Merges all links in the lattice among two EscapeSets. On return, the
	 * newNode will have its old links as well as all links from the oldNode.
	 * The oldNode has all its links removed.
	 * 
	 * @param newNode
	 *            {@code non-null;} the EscapeSet to merge all links into
	 * @param oldNode
	 *            {@code non-null;} the EscapeSet to remove all links from
	 */
	private void replaceNode(EscapeSet newNode, EscapeSet oldNode) {
		for (EscapeSet e : oldNode.parentSets) {
			e.childSets.remove(oldNode);
			e.childSets.add(newNode);
			newNode.parentSets.add(e);
		}
		for (EscapeSet e : oldNode.childSets) {
			e.parentSets.remove(oldNode);
			e.parentSets.add(newNode);
			newNode.childSets.add(e);
		}
	}

	/**
	 * Performs escape analysis on a method. Finds scalar replaceable arrays and
	 * replaces them with equivalent registers.
	 * 
	 * @param ssaMethod
	 *            {@code non-null;} method to process
	 */
	public static void process(SsaMethod ssaMethod) {
		new EscapeAnalysis(ssaMethod).run();
	}

	/**
	 * Process a single instruction, looking for new objects resulting from move
	 * result or move param.
	 * 
	 * @param insn
	 *            {@code non-null;} instruction to process
	 */
	private void processInsn(SsaInsn insn) {
		int op = insn.getOpcode().getOpcode();
		RegisterSpec result = insn.getResult();
		EscapeSet escSet;

		// Identify new objects
		if (op == RegOps.MOVE_RESULT_PSEUDO
				&& result.getTypeBearer().getBasicType() == Type.BT_OBJECT) {
			// Handle objects generated through move_result_pseudo
			escSet = processMoveResultPseudoInsn(insn);
			processRegister(result, escSet);
		} else if (op == RegOps.MOVE_PARAM
				&& result.getTypeBearer().getBasicType() == Type.BT_OBJECT) {
			// Track method arguments that are objects
			escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE);
			latticeValues.add(escSet);
			processRegister(result, escSet);
		} else if (op == RegOps.MOVE_RESULT
				&& result.getTypeBearer().getBasicType() == Type.BT_OBJECT) {
			// Track method return values that are objects
			escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE);
			latticeValues.add(escSet);
			processRegister(result, escSet);
		}
	}

	/**
	 * Determine the origin of a move result pseudo instruction that generates
	 * an object. Creates a new EscapeSet for the new object accordingly.
	 * 
	 * @param insn
	 *            {@code non-null;} move result pseudo instruction to process
	 * @return {@code non-null;} an EscapeSet for the object referred to by the
	 *         move result pseudo instruction
	 */
	private EscapeSet processMoveResultPseudoInsn(SsaInsn insn) {
		RegisterSpec result = insn.getResult();
		SsaInsn prevSsaInsn = getInsnForMove(insn);
		int prevOpcode = prevSsaInsn.getOpcode().getOpcode();
		EscapeSet escSet;
		RegisterSpec prevSource;

		switch (prevOpcode) {
		// New instance / Constant
		case RegOps.NEW_INSTANCE:
		case RegOps.CONST:
			escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE);
			break;
		// New array
		case RegOps.NEW_ARRAY:
		case RegOps.FILLED_NEW_ARRAY:
			prevSource = prevSsaInsn.getSources().get(0);
			if (prevSource.getTypeBearer().isConstant()) {
				// New fixed array
				escSet = new EscapeSet(result.getReg(), regCount,
						EscapeState.NONE);
				escSet.replaceableArray = true;
			} else {
				// New variable array
				escSet = new EscapeSet(result.getReg(), regCount,
						EscapeState.GLOBAL);
			}
			break;
		// Loading a static object
		case RegOps.GET_STATIC:
			escSet = new EscapeSet(result.getReg(), regCount,
					EscapeState.GLOBAL);
			break;
		// Type cast / load an object from a field or array
		case RegOps.CHECK_CAST:
		case RegOps.GET_FIELD:
		case RegOps.AGET:
			prevSource = prevSsaInsn.getSources().get(0);
			int setIndex = findSetIndex(prevSource);

			// Set should already exist, try to find it
			if (setIndex != latticeValues.size()) {
				escSet = latticeValues.get(setIndex);
				escSet.regSet.set(result.getReg());
				return escSet;
			}

			// Set not found, must be either null or unknown
			if (prevSource.getType() == Type.KNOWN_NULL) {
				escSet = new EscapeSet(result.getReg(), regCount,
						EscapeState.NONE);
			} else {
				escSet = new EscapeSet(result.getReg(), regCount,
						EscapeState.GLOBAL);
			}
			break;
		default:
			return null;
		}

		// Add the newly created escSet to the lattice and return it
		latticeValues.add(escSet);
		return escSet;
	}

	/**
	 * Iterate through all the uses of a new object.
	 * 
	 * @param result
	 *            {@code non-null;} register where new object is stored
	 * @param escSet
	 *            {@code non-null;} EscapeSet for the new object
	 */
	private void processRegister(RegisterSpec result, EscapeSet escSet) {
		ArrayList<RegisterSpec> regWorklist = new ArrayList<RegisterSpec>();
		regWorklist.add(result);

		// Go through the worklist
		while (!regWorklist.isEmpty()) {
			int listSize = regWorklist.size() - 1;
			RegisterSpec def = regWorklist.remove(listSize);
			List<SsaInsn> useList = ssaMeth.getUseListForRegister(def.getReg());

			// Handle all the uses of this register
			for (SsaInsn use : useList) {
				Rop useOpcode = use.getOpcode();

				if (useOpcode == null) {
					// Handle phis
					processPhiUse(use, escSet, regWorklist);
				} else {
					// Handle other opcodes
					processUse(def, use, escSet, regWorklist);
				}
			}
		}
	}

	/**
	 * Handles phi uses of new objects. Will merge together the sources of a phi
	 * into a single EscapeSet. Adds the result of the phi to the worklist so
	 * its uses can be followed.
	 * 
	 * @param use
	 *            {@code non-null;} phi use being processed
	 * @param escSet
	 *            {@code non-null;} EscapeSet for the object
	 * @param regWorklist
	 *            {@code non-null;} worklist of instructions left to process for
	 *            this object
	 */
	private void processPhiUse(SsaInsn use, EscapeSet escSet,
			ArrayList<RegisterSpec> regWorklist) {
		int setIndex = findSetIndex(use.getResult());
		if (setIndex != latticeValues.size()) {
			// Check if result is in a set already
			EscapeSet mergeSet = latticeValues.get(setIndex);
			if (mergeSet != escSet) {
				// If it is, merge the sets and states, then delete the copy
				escSet.replaceableArray = false;
				escSet.regSet.or(mergeSet.regSet);
				if (escSet.escape.compareTo(mergeSet.escape) < 0) {
					escSet.escape = mergeSet.escape;
				}
				replaceNode(escSet, mergeSet);
				latticeValues.remove(setIndex);
			}
		} else {
			// If no set is found, add it to this escSet and the worklist
			escSet.regSet.set(use.getResult().getReg());
			regWorklist.add(use.getResult());
		}
	}

	/**
	 * Handles non-phi uses of new objects. Checks to see how instruction is
	 * used and updates the escape state accordingly.
	 * 
	 * @param def
	 *            {@code non-null;} register holding definition of new object
	 * @param use
	 *            {@code non-null;} use of object being processed
	 * @param escSet
	 *            {@code non-null;} EscapeSet for the object
	 * @param regWorklist
	 *            {@code non-null;} worklist of instructions left to process for
	 *            this object
	 */
	private void processUse(RegisterSpec def, SsaInsn use, EscapeSet escSet,
			ArrayList<RegisterSpec> regWorklist) {
		int useOpcode = use.getOpcode().getOpcode();
		switch (useOpcode) {
		case RegOps.MOVE:
			// Follow uses of the move by adding it to the worklist
			escSet.regSet.set(use.getResult().getReg());
			regWorklist.add(use.getResult());
			break;
		case RegOps.IF_EQ:
		case RegOps.IF_NE:
		case RegOps.CHECK_CAST:
			// Compared objects can't be replaced, so promote if necessary
			if (escSet.escape.compareTo(EscapeState.METHOD) < 0) {
				escSet.escape = EscapeState.METHOD;
			}
			break;
		case RegOps.APUT:
			// For array puts, check for a constant array index
			RegisterSpec putIndex = use.getSources().get(2);
			if (!putIndex.getTypeBearer().isConstant()) {
				// If not constant, array can't be replaced
				escSet.replaceableArray = false;
			}
			// Intentional fallthrough
		case RegOps.PUT_FIELD:
			// Skip non-object puts
			RegisterSpec putValue = use.getSources().get(0);
			if (putValue.getTypeBearer().getBasicType() != Type.BT_OBJECT) {
				break;
			}
			escSet.replaceableArray = false;

			// Raise 1st object's escape state to 2nd if 2nd is higher
			RegisterSpecList sources = use.getSources();
			if (sources.get(0).getReg() == def.getReg()) {
				int setIndex = findSetIndex(sources.get(1));
				if (setIndex != latticeValues.size()) {
					EscapeSet parentSet = latticeValues.get(setIndex);
					addEdge(parentSet, escSet);
					if (escSet.escape.compareTo(parentSet.escape) < 0) {
						escSet.escape = parentSet.escape;
					}
				}
			} else {
				int setIndex = findSetIndex(sources.get(0));
				if (setIndex != latticeValues.size()) {
					EscapeSet childSet = latticeValues.get(setIndex);
					addEdge(escSet, childSet);
					if (childSet.escape.compareTo(escSet.escape) < 0) {
						childSet.escape = escSet.escape;
					}
				}
			}
			break;
		case RegOps.AGET:
			// For array gets, check for a constant array index
			RegisterSpec getIndex = use.getSources().get(1);
			if (!getIndex.getTypeBearer().isConstant()) {
				// If not constant, array can't be replaced
				escSet.replaceableArray = false;
			}
			break;
		case RegOps.PUT_STATIC:
			// Static puts cause an object to escape globally
			escSet.escape = EscapeState.GLOBAL;
			break;
		case RegOps.INVOKE_STATIC:
		case RegOps.INVOKE_VIRTUAL:
		case RegOps.INVOKE_SUPER:
		case RegOps.INVOKE_DIRECT:
		case RegOps.INVOKE_INTERFACE:
		case RegOps.RETURN:
		case RegOps.THROW:
			// These operations cause an object to escape interprocedurally
			escSet.escape = EscapeState.INTER;
			break;
		default:
			break;
		}
	}

	/**
	 * Performs scalar replacement on all eligible arrays.
	 */
	private void scalarReplacement() {
		// Iterate through lattice, looking for non-escaping replaceable arrays
		for (EscapeSet escSet : latticeValues) {
			if (!escSet.replaceableArray || escSet.escape != EscapeState.NONE) {
				continue;
			}

			// Get the instructions for the definition and move of the array
			int e = escSet.regSet.nextSetBit(0);
			SsaInsn def = ssaMeth.getDefinitionForRegister(e);
			SsaInsn prev = getInsnForMove(def);

			// Create a map for the new registers that will be created
			TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer();
			int length = ((CstLiteralBits) lengthReg).getIntBits();
			ArrayList<RegisterSpec> newRegs = new ArrayList<RegisterSpec>(
					length);
			HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>();

			// Replace the definition of the array with registers
			replaceDef(def, prev, length, newRegs);

			// Mark definition instructions for deletion
			deletedInsns.add(prev);
			deletedInsns.add(def);

			// Go through all uses of the array
			List<SsaInsn> useList = ssaMeth.getUseListForRegister(e);
			for (SsaInsn use : useList) {
				// Replace the use with scalars and then mark it for deletion
				replaceUse(use, prev, newRegs, deletedInsns);
				deletedInsns.add(use);
			}

			// Delete all marked instructions
			ssaMeth.deleteInsns(deletedInsns);
			ssaMeth.onInsnsChanged();

			// Convert the method back to SSA form
			SsaConverter.updateSsaMethod(ssaMeth, regCount);

			// Propagate and remove extra moves added by scalar replacement
			movePropagate();
		}
	}

	/**
	 * Replaces the instructions that define an array with equivalent registers.
	 * For each entry in the array, a register is created, initialized to zero.
	 * A mapping between this register and the corresponding array index is
	 * added.
	 * 
	 * @param def
	 *            {@code non-null;} move result instruction for array
	 * @param prev
	 *            {@code non-null;} instruction for instantiating new array
	 * @param length
	 *            size of the new array
	 * @param newRegs
	 *            {@code non-null;} mapping of array indices to new registers to
	 *            be populated
	 */
	private void replaceDef(SsaInsn def, SsaInsn prev, int length,
			ArrayList<RegisterSpec> newRegs) {
		Type resultType = def.getResult().getType();

		// Create new zeroed out registers for each element in the array
		for (int i = 0; i < length; i++) {
			Constant newZero = Zeroes.zeroFor(resultType.getComponentType());
			TypedConstant typedZero = (TypedConstant) newZero;
			RegisterSpec newReg = RegisterSpec.make(ssaMeth.makeNewSsaReg(),
					typedZero);
			newRegs.add(newReg);
			insertPlainInsnBefore(def, RegisterSpecList.EMPTY, newReg,
					RegOps.CONST, newZero);
		}
	}

	/**
	 * Replaces the use for a scalar replaceable array. Gets and puts become
	 * move instructions, and array lengths and fills are handled. Can also
	 * identify ArrayIndexOutOfBounds exceptions and throw them if detected.
	 * 
	 * @param use
	 *            {@code non-null;} move result instruction for array
	 * @param prev
	 *            {@code non-null;} instruction for instantiating new array
	 * @param newRegs
	 *            {@code non-null;} mapping of array indices to new registers
	 * @param deletedInsns
	 *            {@code non-null;} set of instructions marked for deletion
	 */
	private void replaceUse(SsaInsn use, SsaInsn prev,
			ArrayList<RegisterSpec> newRegs, HashSet<SsaInsn> deletedInsns) {
		int index;
		int length = newRegs.size();
		SsaInsn next;
		RegisterSpecList sources;
		RegisterSpec source, result;
		CstLiteralBits indexReg;

		switch (use.getOpcode().getOpcode()) {
		case RegOps.AGET:
			// Replace array gets with moves
			next = getMoveForInsn(use);
			sources = use.getSources();
			indexReg = ((CstLiteralBits) sources.get(1).getTypeBearer());
			index = indexReg.getIntBits();
			if (index < length) {
				source = newRegs.get(index);
				result = source.withReg(next.getResult().getReg());
				insertPlainInsnBefore(next, RegisterSpecList.make(source),
						result, RegOps.MOVE, null);
			} else {
				// Throw an exception if the index is out of bounds
				insertExceptionThrow(next, sources.get(1), deletedInsns);
				deletedInsns.add(next.getBlock().getInsns().get(2));
			}
			deletedInsns.add(next);
			break;
		case RegOps.APUT:
			// Replace array puts with moves
			sources = use.getSources();
			indexReg = ((CstLiteralBits) sources.get(2).getTypeBearer());
			index = indexReg.getIntBits();
			if (index < length) {
				source = sources.get(0);
				result = source.withReg(newRegs.get(index).getReg());
				insertPlainInsnBefore(use, RegisterSpecList.make(source),
						result, RegOps.MOVE, null);
				// Update the newReg entry to mark value as unknown now
				newRegs.set(index, result.withSimpleType());
			} else {
				// Throw an exception if the index is out of bounds
				insertExceptionThrow(use, sources.get(2), deletedInsns);
			}
			break;
		case RegOps.ARRAY_LENGTH:
			// Replace array lengths with const instructions
			TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer();
			// CstInteger lengthReg = CstInteger.make(length);
			next = getMoveForInsn(use);
			insertPlainInsnBefore(next, RegisterSpecList.EMPTY,
					next.getResult(), RegOps.CONST, (Constant) lengthReg);
			deletedInsns.add(next);
			break;
		case RegOps.MARK_LOCAL:
			// Remove mark local instructions
			break;
		case RegOps.FILL_ARRAY_DATA:
			// Create const instructions for each fill value
			Insn ropUse = use.getOriginalRopInsn();
			FillArrayDataInsn fill = (FillArrayDataInsn) ropUse;
			ArrayList<Constant> constList = fill.getInitValues();
			for (int i = 0; i < length; i++) {
				RegisterSpec newFill = RegisterSpec.make(newRegs.get(i)
						.getReg(), (TypeBearer) constList.get(i));
				insertPlainInsnBefore(use, RegisterSpecList.EMPTY, newFill,
						RegOps.CONST, constList.get(i));
				// Update the newRegs to hold the new const value
				newRegs.set(i, newFill);
			}
			break;
		default:
		}
	}

	/**
	 * Identifies extra moves added by scalar replacement and propagates the
	 * source of the move to any users of the result.
	 */
	private void movePropagate() {
		for (int i = 0; i < ssaMeth.getRegCount(); i++) {
			SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

			// Look for move instructions only
			if (insn == null || insn.getOpcode() == null
					|| insn.getOpcode().getOpcode() != RegOps.MOVE) {
				continue;
			}

			final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy();
			final RegisterSpec source = insn.getSources().get(0);
			final RegisterSpec result = insn.getResult();

			// Ignore moves that weren't added due to scalar replacement
			if (source.getReg() < regCount && result.getReg() < regCount) {
				continue;
			}

			// Create a mapping from source to result
			RegisterMapper mapper = new RegisterMapper() {

				@Override
				public int getNewRegisterCount() {
					return ssaMeth.getRegCount();
				}

				@Override
				public RegisterSpec map(RegisterSpec registerSpec) {
					if (registerSpec.getReg() == result.getReg()) {
						return source;
					}

					return registerSpec;
				}
			};

			// Modify all uses of the move to use the source of the move instead
			for (SsaInsn use : useList[result.getReg()]) {
				use.mapSourceRegisters(mapper);
			}
		}
	}

	/**
	 * Runs escape analysis and scalar replacement of arrays.
	 */
	private void run() {
		ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() {

			public void visitBlock(SsaBasicBlock block, SsaBasicBlock unused) {
				block.forEachInsn(new SsaInsn.Visitor() {

					public void visitMoveInsn(NormalSsaInsn insn) {
						// do nothing
					}

					public void visitPhiInsn(PhiInsn insn) {
						// do nothing
					}

					public void visitNonMoveInsn(NormalSsaInsn insn) {
						processInsn(insn);
					}
				});
			}
		});

		// Go through lattice and promote fieldSets as necessary
		for (EscapeSet e : latticeValues) {
			if (e.escape != EscapeState.NONE) {
				for (EscapeSet field : e.childSets) {
					if (e.escape.compareTo(field.escape) > 0) {
						field.escape = e.escape;
					}
				}
			}
		}

		// Perform scalar replacement for arrays
		scalarReplacement();
	}

	/**
	 * Replaces instructions that trigger an ArrayIndexOutofBounds exception
	 * with an actual throw of the exception.
	 * 
	 * @param insn
	 *            {@code non-null;} instruction causing the exception
	 * @param index
	 *            {@code non-null;} index value that is out of bounds
	 * @param deletedInsns
	 *            {@code non-null;} set of instructions marked for deletion
	 */
	private void insertExceptionThrow(SsaInsn insn, RegisterSpec index,
			HashSet<SsaInsn> deletedInsns) {
		// Create a new ArrayIndexOutOfBoundsException
		CstType exception = new CstType(
				Exceptions.TYPE_ArrayIndexOutOfBoundsException);
		insertThrowingInsnBefore(insn, RegisterSpecList.EMPTY, null,
				RegOps.NEW_INSTANCE, exception);

		// Add a successor block with a move result pseudo for the exception
		SsaBasicBlock currBlock = insn.getBlock();
		SsaBasicBlock newBlock = currBlock.insertNewSuccessor(currBlock
				.getPrimarySuccessor());
		SsaInsn newInsn = newBlock.getInsns().get(0);
		RegisterSpec newReg = RegisterSpec.make(ssaMeth.makeNewSsaReg(),
				exception);
		insertPlainInsnBefore(newInsn, RegisterSpecList.EMPTY, newReg,
				RegOps.MOVE_RESULT_PSEUDO, null);

		// Add another successor block to initialize the exception
		SsaBasicBlock newBlock2 = newBlock.insertNewSuccessor(newBlock
				.getPrimarySuccessor());
		SsaInsn newInsn2 = newBlock2.getInsns().get(0);
		CstNat newNat = new CstNat(new CstString("<init>"), new CstString(
				"(I)V"));
		CstMethodRef newRef = new CstMethodRef(exception, newNat);
		insertThrowingInsnBefore(newInsn2,
				RegisterSpecList.make(newReg, index), null,
				RegOps.INVOKE_DIRECT, newRef);
		deletedInsns.add(newInsn2);

		// Add another successor block to throw the new exception
		SsaBasicBlock newBlock3 = newBlock2.insertNewSuccessor(newBlock2
				.getPrimarySuccessor());
		SsaInsn newInsn3 = newBlock3.getInsns().get(0);
		insertThrowingInsnBefore(newInsn3, RegisterSpecList.make(newReg), null,
				RegOps.THROW, null);
		newBlock3.replaceSuccessor(newBlock3.getPrimarySuccessorIndex(),
				ssaMeth.getExitBlock().getIndex());
		deletedInsns.add(newInsn3);
	}

	/**
	 * Inserts a new PlainInsn before the given instruction. TODO: move this
	 * somewhere more appropriate
	 * 
	 * @param insn
	 *            {@code non-null;} instruction to insert before
	 * @param newSources
	 *            {@code non-null;} sources of new instruction
	 * @param newResult
	 *            {@code non-null;} result of new instruction
	 * @param newOpcode
	 *            opcode of new instruction
	 * @param cst
	 *            {@code null-ok;} constant for new instruction, if any
	 */
	private void insertPlainInsnBefore(SsaInsn insn,
			RegisterSpecList newSources, RegisterSpec newResult, int newOpcode,
			Constant cst) {

		Insn originalRopInsn = insn.getOriginalRopInsn();
		Rop newRop;
		if (newOpcode == RegOps.MOVE_RESULT_PSEUDO) {
			newRop = Rops.opMoveResultPseudo(newResult.getType());
		} else {
			newRop = Rops.ropFor(newOpcode, newResult, newSources, cst);
		}

		Insn newRopInsn;
		if (cst == null) {
			newRopInsn = new PlainInsn(newRop, originalRopInsn.getPosition(),
					newResult, newSources);
		} else {
			newRopInsn = new PlainCstInsn(newRop,
					originalRopInsn.getPosition(), newResult, newSources, cst);
		}

		NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock());
		List<SsaInsn> insns = insn.getBlock().getInsns();

		insns.add(insns.lastIndexOf(insn), newInsn);
		ssaMeth.onInsnAdded(newInsn);
	}

	/**
	 * Inserts a new ThrowingInsn before the given instruction. TODO: move this
	 * somewhere more appropriate
	 * 
	 * @param insn
	 *            {@code non-null;} instruction to insert before
	 * @param newSources
	 *            {@code non-null;} sources of new instruction
	 * @param newResult
	 *            {@code non-null;} result of new instruction
	 * @param newOpcode
	 *            opcode of new instruction
	 * @param cst
	 *            {@code null-ok;} constant for new instruction, if any
	 */
	private void insertThrowingInsnBefore(SsaInsn insn,
			RegisterSpecList newSources, RegisterSpec newResult, int newOpcode,
			Constant cst) {

		Insn origRopInsn = insn.getOriginalRopInsn();
		Rop newRop = Rops.ropFor(newOpcode, newResult, newSources, cst);
		Insn newRopInsn;
		if (cst == null) {
			newRopInsn = new ThrowingInsn(newRop, origRopInsn.getPosition(),
					newSources, StdTypeList.EMPTY);
		} else {
			newRopInsn = new ThrowingCstInsn(newRop, origRopInsn.getPosition(),
					newSources, StdTypeList.EMPTY, cst);
		}

		NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock());
		List<SsaInsn> insns = insn.getBlock().getInsns();

		insns.add(insns.lastIndexOf(insn), newInsn);
		ssaMeth.onInsnAdded(newInsn);
	}
}
